#include <iostream>
using namespace std;
// TIP 要<b>Run</b>代码，请按 <shortcut actionId="Run"/> 或点击装订区域中的 <icon src="AllIcons.Actions.Execute"/> 图标。
struct Vec2 {
    double x, y;

    Vec2(double _x = 0, double _y = 0) : x(_x), y(_y) {}

    // 减法运算符：B - A 得到向量 AB
    Vec2 operator-(const Vec2& other) const {
        return Vec2(x - other.x, y - other.y);
    }

    // 计算长度（模）
    double length() const {
        return std::sqrt(x * x + y * y);
    }

    // 点积
    double dot(const Vec2& other) const {
        return x * other.x + y * other.y;
    }

    // 单位向量化
    Vec2 normalized() const {
        double len = length();
        if (len == 0) return Vec2(0, 0);
        return Vec2(x / len, y / len);
    }
};

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
using namespace std;

struct State {
    int a, b, c; // 三个桶的当前水量
    State(int _a, int _b, int _c) : a(_a), b(_b), c(_c) {}
    bool operator<(const State& other) const {
        return tie(a, b, c) < tie(other.a, other.b, other.c);
    }
};

// 倒水函数：从x桶往y桶倒
pair<int, int> pour(int from, int to, int cap_to) {
    int move = min(from, cap_to - to);
    return {from - move, to + move};
}

// 打印路径
void printPath(map<State, State>& parent, State& target) {
    vector<State> path;
    State cur = target;
    while (parent.count(cur)) {
        path.push_back(cur);
        cur = parent[cur];
    }
    path.push_back(cur);
    reverse(path.begin(), path.end());

    for (size_t i = 0; i < path.size(); ++i) {
        printf("Step %2lu: A=%d, B=%d, C=%d\n", i, path[i].a, path[i].b, path[i].c);
    }
}

void solve() {
    const int capA = 10, capB = 7, capC = 3;
    queue<State> q;
    set<State> visited;
    map<State, State> parent;

    State start(10, 0, 0);
    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        State cur = q.front(); q.pop();

        int a = cur.a, b = cur.b, c = cur.c;
        if (a == 5 || b == 5 || c == 5) {
            cout << "Found solution:\n";
            printPath(parent, cur);
            return;
        }

        // 枚举所有可能的倒水操作（6种）
        vector<tuple<int, int, int>> nextStates;
        // A → B
        auto [na, nb] = pour(a, b, capB); nextStates.push_back({na, nb, c});
        // A → C
        tie(na, nb) = pour(a, c, capC); nextStates.push_back({na, b, nb});
        // B → A
        tie(nb, na) = pour(b, a, capA); nextStates.push_back({na, nb, c});
        // B → C
        tie(nb, na) = pour(b, c, capC); nextStates.push_back({a, nb, na});
        // C → A
        tie(nc, na) = pour(c, a, capA); nextStates.push_back({na, b, nc});
        // C → B
        tie(nc, na) = pour(c, b, capB); nextStates.push_back({a, na, nc});

        for (auto& [x, y, z] : nextStates) {
            State next(x, y, z);
            if (!visited.count(next)) {
                visited.insert(next);
                parent[next] = cur;
                q.push(next);
            }
        }
    }

    cout << " No solution found.\n";
}

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* slow = head, *fast = head, *prev = nullptr;
    while(n)
    {
        if(fast == nullptr) return nullptr;
        fast = fast->next;
        n--;
    }
    while(fast)
    {
        prev = slow;
        slow = slow->next;
        fast = fast->next;
    }

    if(slow == head) return slow->next;
    prev->next = slow->next;
    delete slow;
    return head;
}

int main() {
    solve();
    return 0;
}
